#include <iostream>
#include <vector>

using namespace std;
// 22.括号生成
// 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
// 例如，给出n = 3，生成的结果为：["((()))","(()())","(())()","()(())","()()()"]

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if(n < 1) {
            return res;
        }
        string s;
        res.clear();
        generateOneByOne(n, 0, 0, s);
        return res;
    }

private:
    vector<string> res;
    // left：当前用了多少个左括号 right：当前用了多少右括号 result：当前生成的字符串
    void generateOneByOne(int n, int left, int right, string &curStr) {
        if(left == n && right == n) {
            cout<<"one ans : "<<curStr<<endl;
            res.push_back(curStr);
            return;
        }
        if(left < n) {
            generateOneByOne(n, left+1, right, curStr.append("("));
            curStr.pop_back();
        }
        if(right < n && left >right) {
            generateOneByOne(n, left,right+1,curStr.append(")"));
            curStr.pop_back();
        }
    }
};
void printRes(vector<string> &res) {
    cout << "[";
    for(string& s: res) {
        cout << s << ",";
    }
    cout << "]" << endl;
}
int main() {
    vector<string> res = Solution().generateParenthesis(2);
    printRes(res);
    return 0;
}
